package clases;
import java.math.BigInteger;


public class karatsuba {

	/**
	 * @param args
	 */
	
	
	public static BigInteger Karatsuba(BigInteger x,BigInteger y){
		
		int posiciones = Math.max(x.bitLength(), y.bitLength());
		
		// para n menor que 1000 multiplicamos por BigInteger
		// problema facil de resolver
		if (posiciones <= 1000){
			return x.multiply(y);
		}
		
		posiciones = posiciones /2;
		
		// armamos x1,x2,y de la misma manera y1,y2
		// los subproblemas
		
		BigInteger x1 = x.shiftRight(posiciones);
		BigInteger x2 = x.subtract(x1.shiftLeft(posiciones));
		BigInteger y1 = y.shiftRight(posiciones);
		BigInteger y2 = y.shiftLeft(posiciones);
		
		// calculamosm los subproblemas
		
		BigInteger a = Karatsuba(x1, y1);
		BigInteger b =Karatsuba(x2, y2);
		BigInteger c =Karatsuba(x2.add(x1), y2.add(y1));
		BigInteger k= c.subtract(a).subtract(b);
		
		// obtenemos el resultado general
		return a.shiftLeft(2 * posiciones).add(k.shiftLeft(posiciones)).add(b);
		
		
		
		
	}
	public static void main(String[] args) {
		
		BigInteger a = new BigInteger("00000000000000000000000000000000000000000001");
		BigInteger b = new BigInteger("000000000000000000000000000000000000000000000000000000000000000002");
		System.out.println(Karatsuba(a,b));
		
		
		
		

	}

}
